#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef char ElementType;

typedef struct TreeNode
{
    ElementType data;
    TreeNode *lChild;
    TreeNode *rChild;
} TreeNode, *Tree;

typedef struct QueueNode
{
    TreeNode *data;
    QueueNode *next;
} QueueNode, *Queue;

/*尾插法入队*/
bool EnQueue(Queue queue, TreeNode *tree_node)
{
    QueueNode *q_node = queue;
    while (q_node->next)
    {
        q_node = q_node->next;
    }
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = tree_node;
    node->next = q_node->next;
    q_node->next = node;
    return true;
}

/*出队*/
bool DeQueue(Queue queue, Tree &tree_node)
{
    if (!queue->next)
    {
        return false;
    }
    QueueNode *tmp_node = queue->next;
    tree_node = tmp_node->data;
    queue->next = tmp_node->next;
    free(tmp_node);
    return true;
}

void BuildBTree(TreeNode *root, ElementType ch[])
{
    int len = strlen(ch);
    Queue queue = (Queue)malloc(sizeof(QueueNode));
    EnQueue(queue, root);
    for (int i = 0; i < len; i++)
    {
        TreeNode *tree_node;
        DeQueue(queue, tree_node);
        tree_node->data = ch[i];
        Tree left = new TreeNode();
        Tree right = new TreeNode();
        tree_node->lChild = left;
        tree_node->rChild = right;
        EnQueue(queue, left);
        EnQueue(queue, right);
    }
}

void preOrderTree(Tree tree)
{
    if (tree)
    {
        printf("%c", tree->data);
    }
    if (tree->lChild)
    {
        preOrderTree(tree->lChild);
    }
    if (tree->rChild)
    {
        preOrderTree(tree->rChild);
    }
}

int main()
{
    Tree tree = new TreeNode();
    char str[] = "abcdefghijk";
    BuildBTree(tree, str);
    preOrderTree(tree);
    return 0;
}